Masala #1156

Xotira 256 MB Vaqt 3000 ms Qiyinchiligi 40 %

3.5 (Baholar 8)

Robolandiya poyezdlari

Robolandiya mamlakatida $N$ ta shahar mavjud. Har bir shahar ketma-ket joylashgan va har biri tartib bilan raqamlangan. Bundan tashqari, ushbu shaharlar orasida qatnovchi $M$ ta poyezd bor. $i-$ poyezd $L_i$ - $R_i$ shaharlari orasida qatnaydi $(1 \le L_i \le R_i \le N)$ .

Robolandiya qiroli ushbu poyezdlarga qiziqib qoldi va endi u vazirlaridan so'ramoqda: ″ $p_i$ va $q_i$ shaharlari orasida qatnovchi nechta poyezd bor?″.

Sizning vazifangiz quyidagi shartni qanoatlantiruvchi poyezdlar sonini topishdir.

$p_i \le L_j \le R_j \le q_i$ .

Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida uchta butun son - N, M, Q - shaharlar, poyezdlar va so'rovlar soni $(1 \le N \le 500, 1 \le M , Q \le 2*10^6)$ .

Keyingi M ta qatorning har birida bo'shliq bilan ajratilgan ikkita butun son - $L_i$ va $R_i$ mavjud.

Keyingi Q ta qatorning har birida bo'shliq bilan ajratilgan ikkita butun son - $p_i$ va $q_i$ mavjud.

Chiquvchi ma'lumotlar:

Chiqish faylining Q ta qatorida, har bir so'rov uchun ushbu oraliqda harakatlanuvchi poyezdlar sonini chop eting.

Misollar

#	input.txt	output.txt
1	2 3 1 1 1 1 2 2 2 1 2	3
2	5 10 5 3 4 1 4 1 2 1 1 2 5 2 5 1 2 1 3 3 5 3 4 1 2 1 1 5 5 1 5 2 4	3 1 0 10 2

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin